﻿#define _CRT_SECURE_NO_WARNINGS 
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        for (int cur = 0, dest = -1; cur < nums.size(); cur++)
            if (nums[cur]) // 处理⾮零元素
                swap(nums[++dest], nums[cur]);
    }
};



/////////////////////////////////////////////////////////////////

class Solution {
public:
    void duplicateZeros(vector<int>& arr) {
        int cur = 0, dest = -1, n = arr.size();
        while (cur < n)
        {
            if (arr[cur]) dest++;
            else dest += 2;
            if (dest >= n - 1) break;
            cur++;
        }
        if (dest == n)
        {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        while (cur >= 0)
        {
            if (arr[cur])
                arr[dest--] = arr[cur--];
            else
            {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }
};

//////////////////////////////////////////////////////////

class Solution {
public:

    int Sum(int n)
    {
        int t = 0;
        int ret = 0;
        while (n > 0)
        {
            t = n % 10;
            ret += t * t;
            n = n / 10;
        }
        return ret;
    }
    bool isHappy(int n) {
        int slow = n, fast = Sum(n);
        while (slow != fast)
        {
            slow = Sum(slow);
            fast = Sum(Sum(fast));
        }
        return slow == 1;
    }
};

////////////////////////////////////////////////

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int v = 0;
        int ret = 0;
        while (left < right)
        {
            v = min(height[left], height[right]) * (right - left);
            ret = max(v, ret);
            if (height[left] < height[right])
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return ret;
    }
};


////////////////////////////////////////////////

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ret = 0, n = nums.size();
        for (int i = n - 1; i >= 2; i--)
        {
            int left = 0, right = i - 1;
            while (left < right)
            {
                if (nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
        return ret;
    }
};

////////////////////////////////////////////////////
class Solution {
public:
    vector<int> twoSum(vector<int>& price, int target) {
        sort(price.begin(), price.end());
        int left = 0, right = price.size() - 1;
        while (left < right)
        {
            int sum = price[left] + price[right];
            if (price[left] + price[right] > target)
            {
                right--;
            }
            else if (price[left] + price[right] < target)
            {
                left++;
            }
            else
            {
                return { price[left],price[right] };
            }
        }
        return { -1,-1 };
    }
};